package leetcode;

import util.TreeNode;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0669.java
 * @Author : WangRuoyu
 * @Date 2023/11/15 22:45
 */


public class Q0669 {
    private void dfs(TreeNode node, TreeNode father, int l, int r) {
        if (node != null) {
            if (node.val > r) {
                father.right = node.left;
                dfs(node.left, father, l, r);
            } else if (node.val < l) {
                father.left = node.right;
                dfs(node.right, father, l, r);
            } else {
                dfs(node.left, node, l, r);
                dfs(node.right, node, l, r);
            }
        }
    }

    public TreeNode trimBST(TreeNode root, int low, int high) {
        while (root != null && !(root.val >= low && root.val <= high)) {
            if (root.val < low) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        if (root != null) {
            dfs(root, null, low, high);
        }
        return root;
    }

    public static void main(String[] args) {
        Q0669 sl = new Q0669();
    }
}